package com.squapsource.ibm.june11;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class CircleParker {

	private static final int NUM_SPOTS = 100;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int rounds = 1000000000;
		int carsSum = 0;
		for (long i = 0; i < rounds; i++) {
			carsSum += simulateOneRound();
			if (i % 100000000 == 0) {
				Double avg = ((double) carsSum / i);
				System.out.print("cars: " + carsSum);
				System.out.printf(" Avg: %f\n", avg);
			}
		}
	}

	private static int simulateOneRound() {
		List<Integer> spots = getSpots();
		Random generator = new Random();
		int cars = 0;
		while (spots.size() != 0) {
			int chosenSpot = Math.abs(generator.nextInt()) % NUM_SPOTS;
			if (!spots.contains(chosenSpot)) {
				continue;
			}
			removeSpot(spots, chosenSpot);
			removeSpot(spots, chosenSpot + 1);
			removeSpot(spots, chosenSpot - 1);
			cars++;
		}
		// System.out.println(cars);
		return cars;
	}

	private static void removeSpot(List<Integer> spots, int chosenSpot) {
		if (chosenSpot <0 )
			chosenSpot = chosenSpot + NUM_SPOTS;
		if (chosenSpot >= NUM_SPOTS)
			chosenSpot = chosenSpot % NUM_SPOTS;
		int index = spots.indexOf(chosenSpot);
		if (index >= 0)
			spots.remove(index);
	}

	private static List<Integer> getSpots() {
		List<Integer> spots = new ArrayList<Integer>();
		for (int i = 0; i < NUM_SPOTS; i++) {
			spots.add(i);
		}
		return spots;
	}

}
